package org.example.Soution004;

import java.util.Arrays;

public class SkillColorClassification {
    public static void main(String[] args) {
        SkillColorClassification obj = new SkillColorClassification();
        int[] nums=new int[]{2,0,2,1,1,0};
        obj.sortColors3(nums);
        System.out.println(Arrays.toString(nums));
    }

    //投机取巧，但是好像有点慢
    public void sortColors1(int[] nums) {
        int red=0,white=0,blue=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]==0){
                red++;
            }else if(nums[i]==1){
                white++;
            }else{
                blue++;
            }
        }
        for(int r=0;r<red;r++){
            nums[r]=0;
        }
        for(int w=red;w<red+white;w++){
            nums[w]=1;
        }
        for(int b=red+white;b< nums.length;b++){
            nums[b]=2;
        }
    }

    //来试试快排
    public void sortColors2(int[] nums) {
        quickSort(nums,0,nums.length-1);
    }

    public void quickSort(int[] nums,int low,int high){
        if(low>=high){return;}
        int begin=low,end=high;
        int pivot=nums[low];
        low++;
        while(low<=high){
            while(low<=high&&nums[low]<pivot) low++;
            while(low<=high&&nums[high]>pivot) high--;
            if(low<=high){
                int temp=nums[low];
                nums[low]=nums[high];
                nums[high]=temp;
                low++;
                high--;
            }
        }
        nums[begin]=nums[high];
        nums[high]=pivot;
        quickSort(nums,begin,high-1);
        quickSort(nums,high+1,end);
    }

    public void sortColors3(int[] nums) {
        int n=nums.length;
        int p0=0,p1=0;
        for(int i=0;i<n;i++){
            if(nums[i]==1){
                int tmp=nums[p1];
                nums[p1]=nums[i];
                nums[i]=tmp;
                p1++;
            }else if(nums[i]==0){
                int tmp=nums[p0];
                nums[p0]=nums[i];
                nums[i]=tmp;
                if(nums[i]==1){
                    int temp=nums[p1];
                    nums[p1]=nums[i];
                    nums[i]=temp;
                }
                p0++;
                p1++;
            }
        }
    }
}
